|
|
Computational Homotopy Theory
Krčál, Marek ; Matoušek, Jiří (advisor) ; Pultr, Aleš (referee) ; Romero Ibáñez, Ana (referee)
of doctoral thesis "Computational Homotopy Theory": We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of compu- tational complexity. The extension problem asks, given topological spaces X, Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that A, X, Y are represented as finite simplicial complexes and f as a simplicial map. We study the problem under the assumption that, for some d ≥ 1, Y is d- connected, otherwise the problem is undecidable by uncomputability of the fundamental group; We prove that, this problem is still undecidable for dim X = 2d + 2. On the other hand, for every fixed dim X ≤ 2d + 1, we obtain an algorithm that solves the extension problem in polynomial time. We obtain analogous complexity results for the problem of determining the set of homotopy classes of maps X → Y . We also consider the computation of the homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, we prove that computing πk(Y ) is #P-hard if k is a part of input. It is a strengthening of...
|
|
|
Computational Homotopy Theory
Krčál, Marek ; Matoušek, Jiří (advisor) ; Pultr, Aleš (referee) ; Romero Ibáñez, Ana (referee)
of doctoral thesis "Computational Homotopy Theory": We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of compu- tational complexity. The extension problem asks, given topological spaces X, Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that A, X, Y are represented as finite simplicial complexes and f as a simplicial map. We study the problem under the assumption that, for some d ≥ 1, Y is d- connected, otherwise the problem is undecidable by uncomputability of the fundamental group; We prove that, this problem is still undecidable for dim X = 2d + 2. On the other hand, for every fixed dim X ≤ 2d + 1, we obtain an algorithm that solves the extension problem in polynomial time. We obtain analogous complexity results for the problem of determining the set of homotopy classes of maps X → Y . We also consider the computation of the homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, we prove that computing πk(Y ) is #P-hard if k is a part of input. It is a strengthening of...
|
guest ::
